{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "635d8ebb",
   "metadata": {},
   "source": [
    "# Tree of Thoughts (ToT)\n",
    "\n",
    "- Author: [Sunworl Kim](https://github.com/sunworl)\n",
    "- Peer Review:\n",
    "- Proofread : [fastjw](https://github.com/fastjw)\n",
    "- This is a part of [LangChain Open Tutorial](https://github.com/LangChain-OpenTutorial/LangChain-OpenTutorial)\n",
    "\n",
    "[![Open in Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/LangChain-OpenTutorial/LangChain-OpenTutorial/blob/main/17-LangGraph/03-Use-Cases/13-LangGraph-Tree-of-Thoughts.ipynb)[![Open in GitHub](https://img.shields.io/badge/Open%20in%20GitHub-181717?style=flat-square&logo=github&logoColor=white)](https://github.com/LangChain-OpenTutorial/LangChain-OpenTutorial/blob/main/17-LangGraph/03-Use-Cases/13-LangGraph-Tree-of-Thoughts.ipynb)\n",
    "## Overview\n",
    "\n",
    "Tree of Thoughts (ToT) is a systematic problem-solving framework that enhances language models' reasoning capabilities by exploring and maintaining multiple paths of thought simultaneously. \n",
    "\n",
    "The core concept of ToT breaks down problem-solving processes into multiple stages, where various \"thoughts\" are generated and evaluated at each stage, similar to how a chess player thinks several moves ahead. \n",
    "\n",
    "Each thought represents an independent solution path that the system explores and evaluates in parallel.\n",
    "\n",
    "\n",
    "In this tutorial, we run a \"Make 15\" game that combines four numbers to reach 15 using an LLM agent search algorithm with Tree of Thoughts (ToT).\n",
    "\n",
    "**Main steps**\n",
    "\n",
    "1. Expand: Creative generation phase using LLM to explore all possible equation combinations\n",
    "\n",
    "2. Score: Validation phase that evaluates how accurately generated equations reach the target value of 15\n",
    "\n",
    "3. Prune: Optimization phase that selects only the best candidates to determine the starting point for the next exploration\n",
    "\n",
    "**Key Components** \n",
    "\n",
    "- Reverse-Polish Notation(RPN) Calculator for equation evaluation\n",
    "- LangChain-based solver \n",
    "- State-based graph management\n",
    "\n",
    "**[Note]** This code is substantially derived from the [LangGraph Tree of Thoughts (ToT) tutorial](https://github.com/langchain-ai/langgraph/blob/f239b39060096ab2c8bff0d6303781efee174a5c/docs/docs/tutorials/tot/tot.ipynb).\n",
    "\n",
    "\n",
    "### Table of Contents\n",
    "\n",
    "- [Overview](#overview)\n",
    "- [Environment Setup](#environment-setup)\n",
    "- [Mathematical Equation Exploration and Evaluation Framework](#mathematical-equation-exploration-and-evaluation-framework)\n",
    "- [LLM Configuration for Game Solution Generation](#llm-configuration-for-game-solution-generation)\n",
    "- [Game Solution Explorer](#game-solution-explorer)\n",
    "- [Create Graph](#create-graph)\n",
    "- [Run Graph](#run-graph)\n",
    "\n",
    "\n",
    "### References\n",
    "\n",
    "- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://doi.org/10.48550/arXiv.2305.10601)\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6c7aba4",
   "metadata": {},
   "source": [
    "## Environment Setup\n",
    "\n",
    "Setting up your environment is the first step. See the [Environment Setup](https://wikidocs.net/257836) guide for more details.\n",
    "\n",
    "**[Note]**\n",
    "- The langchain-opentutorial is a package of easy-to-use environment setup guidance, useful functions and utilities for tutorials. \n",
    "- Check out the  [```langchain-opentutorial```](https://github.com/LangChain-OpenTutorial/langchain-opentutorial-pypi) for more details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "21943adb",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%capture --no-stderr\n",
    "%pip install -U langchain-opentutorial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "f25ec196",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Install required packages\n",
    "from langchain_opentutorial import package\n",
    "\n",
    "package.install(\n",
    "    [\n",
    "        \"langsmith\",\n",
    "        \"langchain\",\n",
    "        \"langchain_openai\",\n",
    "        \"langchain_core\",\n",
    "        \"langgraph\"\n",
    "    ],\n",
    "    verbose=False,\n",
    "    upgrade=False,\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9158d8d7",
   "metadata": {},
   "source": [
    "You can set API keys in a ```.env``` file or set them manually.\n",
    "\n",
    "[Note] If you’re not using the ```.env``` file, no worries! Just enter the keys directly in the cell below, and you’re good to go."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7f9065ea",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Environment variables have been set successfully.\n"
     ]
    }
   ],
   "source": [
    "from dotenv import load_dotenv\n",
    "from langchain_opentutorial import set_env\n",
    "\n",
    "# Attempt to load environment variables from a .env file; if unsuccessful, set them manually.\n",
    "if not load_dotenv():\n",
    "    set_env(\n",
    "        {\n",
    "            \"OPENAI_API_KEY\": \"\",\n",
    "            \"LANGCHAIN_API_KEY\": \"\",\n",
    "            \"LANGCHAIN_TRACING_V2\": \"true\",\n",
    "            \"LANGCHAIN_ENDPOINT\": \"https://api.smith.langchain.com\",\n",
    "            \"LANGCHAIN_PROJECT\": \"Tree of Thoughts (ToT)\",\n",
    "        }\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d85dc63",
   "metadata": {},
   "source": [
    "## Mathematical Equation Exploration and Evaluation Framework "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2dd14efe",
   "metadata": {},
   "source": [
    "\n",
    "Define a class that uilizes ```Pydantic``` to calculate RPN formulas.\n",
    "\n",
    "```Pydantic``` is a library that simplifies data validation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "829aed2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import operator\n",
    "from typing import List, Union, Literal, NamedTuple, Optional\n",
    "from pydantic import BaseModel, Field, field_validator\n",
    "\n",
    "# Define the available operators and token type\n",
    "OperatorType = Literal[\"+\", \"-\", \"*\", \"/\"]  \n",
    "TokenType = Union[float, OperatorType]\n",
    "\n",
    "\n",
    "class Equation(BaseModel):\n",
    "    tokens: List[TokenType] = Field(\n",
    "        description=\"The stack of tokens and operators in reverse-polish notation(RPN). Example: [2, 3, '+', 5, '*'] would evaluate to (2 + 3) * 5\"\n",
    "    )\n",
    "\n",
    "    @field_validator('tokens')\n",
    "    def clean_tokens(cls, v):    \n",
    "        return [float(t) if isinstance(t, (int, float)) else t.strip() for t in v]\n",
    "\n",
    "    # Validate operators \n",
    "    def validate_tokens(cls, v): \n",
    "        cleaned_tokens = []\n",
    "        for token in v:\n",
    "            if isinstance(token, str):\n",
    "                token = token.strip()\n",
    "                if token not in {'+', '-', '*', '/'}:\n",
    "                    raise ValueError(f\"Invalid operator: {token}\")\n",
    "            cleaned_tokens.append(token)\n",
    "        return cleaned_tokens\n",
    "    \n",
    "    def compute(self) -> float:\n",
    "        \"\"\"Calculate RPN formula\"\"\"        \n",
    "        op_funcs = {\n",
    "            \"+\": operator.add,\n",
    "            \"-\": operator.sub,\n",
    "            \"*\": operator.mul,\n",
    "            \"/\": operator.truediv,\n",
    "        }\n",
    "        stack = []\n",
    "        for token in self.tokens:\n",
    "            if isinstance(token, float):\n",
    "                stack.append(token)\n",
    "            else:\n",
    "                b, a = stack.pop(), stack.pop()\n",
    "                stack.append(op_funcs[token](a, b))\n",
    "\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96d82b1b",
   "metadata": {},
   "source": [
    "Define a class to organize and store the process of solving mathematical problems, including the generated equations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "874e4c0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "class GuessEquations(BaseModel):\n",
    "  \n",
    "    reasoning: str = Field(\n",
    "        description=\"Detailed explanation of how the formula was created and the process\"\n",
    "    )\n",
    "    equations: List[Equation] = Field(  \n",
    "        description=\"List of generated equations\"\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5fd59592",
   "metadata": {},
   "source": [
    "This signifies a candidate equation that requires evaluation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "1dceac85",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Candidate(NamedTuple):\n",
    "    candidate: Equation              # Equation to be evaluate\n",
    "    score: Optional[float] = None    # Evaluation score of equation\n",
    "    feedback: Optional[str] = None   # Evaluation opinion\n",
    "\n",
    "    # Representation of Output\n",
    "    def __str__(self):\n",
    "        try:\n",
    "            computed = self.candidate.compute()\n",
    "            return f\"Equation({self.candidate.tokens}) = {computed:.2f} (Score: {self.score:.2f if self.score is not None else 'N/A'})\" \n",
    "        except Exception as e:\n",
    "            return f\"Invalid equation: {self.candidate.tokens}; Error: {str(e)}\"\n",
    "\n",
    "class ScoredCandidate(Candidate):\n",
    "    candidate: Equation\n",
    "    score: float\n",
    "    feedback: str        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41180f7b",
   "metadata": {},
   "source": [
    "This Defines the fucdamental structures that are responsible for managing and configuring the state of ToT."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "eea38fff",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing_extensions import Annotated, TypedDict\n",
    "from langchain_core.runnables import RunnableConfig\n",
    "\n",
    "def update_candidates(\n",
    "    existing: Optional[list] = None,\n",
    "    updates: Optional[Union[list, Literal[\"clear\"]]] = None,\n",
    ") -> List[str]:\n",
    "    if existing is None:\n",
    "        existing = []\n",
    "    if updates is None:\n",
    "        return existing\n",
    "    if updates == \"clear\":\n",
    "        return []\n",
    "    # Concatenate the lists\n",
    "    return existing + updates\n",
    "\n",
    "\n",
    "class ToTState(TypedDict):\n",
    "    \n",
    "    problem: str\n",
    "    candidates: Annotated[List[Candidate], update_candidates]\n",
    "    scored_candidates: Annotated[List[ScoredCandidate], update_candidates]\n",
    "    depth: Annotated[int, operator.add]\n",
    "\n",
    "class Configuration(TypedDict, total=False):\n",
    "    max_depth: int\n",
    "    threshold: float\n",
    "    k: int\n",
    "    beam_size: int\n",
    "\n",
    "def _ensure_configurable(config: RunnableConfig) -> Configuration:\n",
    "    configurable = config.get(\"configurable\", {})\n",
    "    return {\n",
    "        **configurable,\n",
    "        \"max_depth\": configurable.get(\"max_depth\", 10),\n",
    "        \"threshold\": config.get(\"threshold\", 1.0),      # success threshold\n",
    "        \"k\": configurable.get(\"k\", 5),                  # Number of candidates to generate\n",
    "        \"beam_size\": configurable.get(\"beam_size\", 3),  # Number of candidates to keep\n",
    "    }\n",
    "\n",
    "class ExpansionState(ToTState):\n",
    "    seed: Optional[Candidate]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dafa6a6a",
   "metadata": {},
   "source": [
    "## LLM Configuration for Game Solution Generation\n",
    "\n",
    "Construct a solution generation pipeline to automate the \"Make 15\" game using LangChain and OpenAI.\n",
    "\n",
    "- ChatPromptTemplate : Generate system prompts that define the rules and objectives of the game."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1a585101",
   "metadata": {},
   "outputs": [],
   "source": [
    "from langchain_core.prompts import ChatPromptTemplate\n",
    "from langchain_openai import ChatOpenAI\n",
    "\n",
    "# Define the Prompt Template\n",
    "prompt = ChatPromptTemplate.from_messages(\n",
    "    [\n",
    "        ( # System prompt: Define the rules of the \"Make 15\" game\n",
    "            \"system\",\n",
    "            \"\"\"You are playing Make 15. Create equations that evaluate to exactly 15 using the provided numbers.\n",
    "            Rules:\n",
    "            1. Use each number exactly once\n",
    "            2. You can use +, -, *, / operators\n",
    "            3. The result must be exactly 15\n",
    "            4. Submit {k} different valid guesses        \n",
    "            Evaluate your guesses carefully before submitting.\"\"\"\n",
    "        ),\n",
    "\n",
    "        ( # User prompt: Includes the number to use and a history of previous attempts\n",
    "            \"user\", \n",
    "            \"Numbers to use: {problem}\\nPrevious attempt (if any): {candidate}\"\n",
    "        ),\n",
    "    ],\n",
    ").partial(candidate=\"\")\n",
    "llm = ChatOpenAI(model=\"gpt-4o-mini\")\n",
    "\n",
    "bound_llm = llm.with_structured_output(GuessEquations)   # Output setting\n",
    "solver = prompt | bound_llm   # Create pipeline"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e41d6171",
   "metadata": {},
   "source": [
    "## Game Solution Explorer\n",
    "\n",
    "Implement a sophisticated search algorithm to solve the \"Make 15\" game."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32a77d9b",
   "metadata": {},
   "source": [
    "A function that calculates the score of a candidate equation, evaluating how far it has reached the target value of 15."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "a6352964",
   "metadata": {},
   "outputs": [],
   "source": [
    "from langchain_core.runnables import RunnableConfig\n",
    "from langgraph.constants import Send\n",
    "from typing import Dict, Any\n",
    "\n",
    "\n",
    "def compute_score(problem: str, candidate: Candidate) -> ScoredCandidate:\n",
    "    numbers = list(map(float, problem.split()))\n",
    "    used_numbers = [\n",
    "        token for token in candidate.candidate.tokens if isinstance(token, (int, float))\n",
    "    ]\n",
    "    # Check if every number is used exactly once\n",
    "    if sorted(used_numbers) != sorted(numbers):\n",
    "        return ScoredCandidate(\n",
    "            candidate=candidate.candidate,\n",
    "            score=0,\n",
    "            feedback=\"The equation must use all 4 numbers exactly once.\"\n",
    "        )\n",
    "    # Score between 0 and 1 based on difference from 15    \n",
    "    try:\n",
    "        result = candidate.candidate.compute()\n",
    "        score = max(0.0, 1.0 - abs(result - 15) / 15)\n",
    "        feedback = f\"Result: {result}\"\n",
    "    except Exception as e:\n",
    "        return ScoredCandidate(\n",
    "            candidate=candidate.candidate,\n",
    "            score=0, \n",
    "            feedback=f\"Invalid equation. Error: {repr(e)}\"\n",
    "        )\n",
    "           \n",
    "    return ScoredCandidate(\n",
    "        candidate=candidate.candidate,\n",
    "        score=score,\n",
    "        feedback=feedback\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f15764e6",
   "metadata": {},
   "source": [
    "Core Algorithm Functions.\n",
    "\n",
    "Calculate the scores for all generated candidate equations and select the candidate equations with the highest scores."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "54c25227",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create new candidates using LLM\n",
    "def expand(state: ExpansionState, *, config: RunnableConfig) -> Dict[str, List[str]]:\n",
    "   configurable = _ensure_configurable(config)\n",
    "\n",
    "   # Ensure problem is a string\n",
    "   problem = state[\"problem\"]\n",
    "   if isinstance(problem, list):\n",
    "       problem = problem[0]\n",
    "\n",
    "   try:\n",
    "        equation_submission = solver.invoke(\n",
    "            {\n",
    "                \"problem\": problem,\n",
    "                \"candidate\": str(state.get(\"seed\", \"\")),\n",
    "                \"k\": configurable[\"k\"],\n",
    "            },\n",
    "            config=config,\n",
    "        )\n",
    "        return {\n",
    "            \"candidates\": [\n",
    "                Candidate(candidate=eq) \n",
    "                for eq in equation_submission.equations\n",
    "                if all(t in {'+', '-', '*', '/'} or isinstance(t, (int, float)) \n",
    "                    for t in eq.tokens)\n",
    "            ]\n",
    "        }\n",
    "   except Exception as e:\n",
    "        return {\"candidates\": []}\n",
    "\n",
    "\n",
    "# Calculate the score for each candidate equation\n",
    "def score(state: ToTState) -> Dict[str, List[ScoredCandidate]]:\n",
    "    candidates = state.get(\"candidates\", [])\n",
    "    if not isinstance(candidates, list):\n",
    "        return {\"scored_candidates\": [], \"candidates\": \"clear\"}        \n",
    "    scored = [\n",
    "        compute_score(state[\"problem\"], candidate) \n",
    "        for candidate in candidates \n",
    "        if hasattr(candidate, 'candidate')\n",
    "    ]\n",
    "    return {\"scored_candidates\": scored, \"candidates\": \"clear\"}\n",
    "\n",
    "\n",
    "# Choose the candidates with the best results\n",
    "# Keep only top candidates as big as beam_size\n",
    "def prune(state: ToTState, *, config: RunnableConfig) -> Dict[str, List[Dict[str, Any]]]:\n",
    "    scored_candidates = state[\"scored_candidates\"]\n",
    "    beam_size = _ensure_configurable(config)[\"beam_size\"]\n",
    "    organized = sorted(\n",
    "        scored_candidates, \n",
    "        key=lambda x: x.score if isinstance(x, ScoredCandidate) else -float('inf'),\n",
    "        reverse=True\n",
    "    )\n",
    "    pruned = organized[:beam_size]\n",
    "    return {\n",
    "        \"candidates\": pruned, # Update the starting point for the next iteration\n",
    "        \"scored_candidates\": \"clear\", # Clear the old memory\n",
    "        \"depth\": 1, # Increment the depth by 1\n",
    "    }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "09175133",
   "metadata": {},
   "source": [
    "Check if the correct answer has been found or if maximum depth has been reached to determine the next step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "4a78248d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def should_terminate(state: ToTState, config: RunnableConfig):\n",
    "    configurable = _ensure_configurable(config)\n",
    "    if not state[\"candidates\"]:\n",
    "        return \"__end__\"\n",
    "    \n",
    "    best_candidate = state[\"candidates\"][0]\n",
    "    solved = isinstance(best_candidate, ScoredCandidate) and abs(best_candidate.score - 1.0) < 1e-6\n",
    "    \n",
    "    if solved or state[\"depth\"] >= configurable[\"max_depth\"]:\n",
    "        return \"__end__\"\n",
    "    \n",
    "    return [Send(\"expand\", {**state, \"seed\": candidate}) for candidate in state[\"candidates\"]]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d911c5ed",
   "metadata": {},
   "source": [
    "## Create Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43fc66dd",
   "metadata": {},
   "source": [
    "Construct a solution exploration graph for the \"Make 15\" game using LangGraph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "88acf1d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "from langgraph.graph import StateGraph\n",
    "from langgraph.checkpoint.memory import MemorySaver\n",
    "\n",
    "# Create the graph\n",
    "def create_graph(config: Configuration = None) -> StateGraph:\n",
    "    if config is None:\n",
    "        config = {\n",
    "            \"max_depth\": 10,\n",
    "            \"threshold\": 1.0,\n",
    "            \"k\": 5,\n",
    "            \"beam_size\": 3\n",
    "        }\n",
    "\n",
    "    builder = StateGraph(state_schema=ToTState, config_schema=Configuration)\n",
    "\n",
    "    # Add nodes : expand, score, prune\n",
    "    builder.add_node(expand)\n",
    "    builder.add_node(score)\n",
    "    builder.add_node(prune)\n",
    "\n",
    "    # Add edges : Define the execution order between nodes\n",
    "    builder.add_edge(\"expand\", \"score\")\n",
    "    builder.add_edge(\"score\", \"prune\")\n",
    "    builder.add_conditional_edges(\"prune\", should_terminate, path_map=[\"expand\", \"__end__\"])\n",
    "\n",
    "    # Set entry point\n",
    "    builder.add_edge(\"__start__\", \"expand\")\n",
    "\n",
    "    return builder.compile(checkpointer=MemorySaver())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7b53696",
   "metadata": {},
   "source": [
    "Visualize the compiled graph structure."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "a974ebbe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAIQAAAGwCAIAAADnulr/AAAAAXNSR0IArs4c6QAAIABJREFUeJztnXdAU+f6x5/sHcIMhC2CLBeKo3UP6qijam3dvR2/1tVxW1tbe9taamtvrbVq1Y5ra6u1WrFanHUhLhwooIAgEEggjBBIQvb8/REv5SoYSM7JOZDz+SuenPd5H/L1Hee8z/u8JLvdDgT4gIy1AwR/Q4iBIwgxcAQhBo4gxMARhBg4goq1A3+jsphymurYFKrCZFCZTTNCogU0xqHaCrx/FvUSUOlXm+vDWNxQJsedXwBjMQw2a0ZNuUTfsrJXv0pdS6WuJZTJMdlsZpu12Wyy2u34/6w2G+02+zl5daVOvS7pMV8qvVjTnMTzc+HXIGH10Fdr0AXSmYWa5kKVYrBvkD+diYkbaLDh3i0KifRJ4rCuFsRGjL8aJEfqKj+MH+L5qj1DtV4TxeaValWpgqDOl8JgADfbbDqLpQcrAQBhLK7FbudRaW/fuWS22zpZytMt49+lN1+ISvRkjdhisFmbzcbkzg0hHm0Z7xflTA2J9mSNmMMkU0IY7D9rxTqrxenNnmsZVrtdaTZ6pi68YQf4+O61zf1GPfo2D4lRoGpUmU2JfFcmfD0Dk81GAghmsh9xjye6KYXJuEda6s1KAACdTNbbLI/urDwhhs5qXh7T1wMV4Ryr3f5R8dVH3OAJMXxpDA6F5oGKHGi1mtyrF7G10C6+NEaqr/BuS3NHN6Auxu81ZXurS9GupRW73T5r8pBzZ45haOERjAsMi+X6dPQt6mJcaqrt7xOIdi2tVEsqlc1Nyf0GdbWgzWZzzGVcttBJjtZVWTuYNKE+m1JZTBZbZx9Bu4S8oe7rDR9du3IeAIYMG/nuR1/mXru06tXnWm94bdVH8xe/AgBSSeW2TeuuX72g12mCgkXj06aveON9AHjvzZcqxWULnlv6446NMpn0xPnCvJs57VpAkJ1VxWnC8P78gIe/Qv2tLRlIKFl+5/Xn5Q21y15bo9Gob167zOHwEpIGjE+blnP5/MZvfgGAqOhYABBXlP7f4umisMh3/vU5nU7fsjH96qUshxji8tKGhrrzZ058sG6LUqng+wjatYAsffn+Hf3vRFeMbIUsu7FmaTTyU6kWtbLw9s1Fz6+YOWchACx8bhkABAYFK1XN8Yl9B6QMddxms9k+Wr3Czy9wx49/sFhsANj61Sd9EvsCgMVikUoqYuISP9v4PYVCcdz/sAXESe34FTW6Y4beauFR6WhY5vEFwaKwQwd2nzx6sO31kqLb8Qn9Wv955dLZu8UFz7/8hkMJrVYjrapw3FAtFZvN5jnPPNeqRLsWEKdGr73SVNfuV+iK8URQxJKIeJSMb/3u9/jEfh+sXvbykhnNTY2OsUHToopP6t96z8XzpygUyri0aY5/lt69Y7fbHS1DXF4CAEl9B7a1+bAFxJEZtDeV8na/QlcMndWitphRMh4eGb31+/3vvP953s2r+/f8AAB3iwoAoE98cus91RJxULCIRrv/lHM9J5tMJsf2SQKAirJSKpUaHhnT1ubDFhAnmMl+zD+43a/QFaNcq/q+shANyybT/XeOU2bMJZFIJrMZACruFQFAQNDffyqNSqfR7veTOp0284+9PgI/JpPlaBlh4dGtOjl42ALiRLC4AzuY66M7gPfi8NXovKl97ZV5oWGRA1KGnjt9jEqlTpg0HQA4PD4AbNn4cXLfFFFYZMrg4f1Shly6cPrYn7/HxMVv27Suob7WoQQAiCvu9er9YBf6sAXEPT/XWDPAJyCG086jH7otg0Ohbeg7AnGzBoM+NCzyUvbpDZ+tUaubv96+NyGxPwA8OePZfgMGZx78dfOXa1VKBQA8s+DFqdPnfrn+/TeWLWQw2PMXv2ww6KVVYqvVKqksj455cOb6sAXEud5cH8ho/90t6g99TWajxmziUD33bgrPqC0mmUH7uF9Iu9+iLkaVXrOj4vZbsQM7ukGn0z45vv1vwyIiqyVVD18fPe6JD9dtQdTN9vlm0ycZ+35++Dqfz1er1e0WeffDDRMnTe/IIAlIfnRGh996YHHpZ8ndvj4BESxuu9/a7fbaGmn7JckksLXjHovN9vVr53UC4qiUzVpNy8PXSaQOfzeBnz+b3X4om9Vu31Ken95xCI+HVvpaLGaTzeqBivDMAVm5iMmeFtxhFICHxDgjr2ZTqHFcgQfqwid2ABqZ7PPI9xEeig4ZHxiWIStTeGtAAgCUtjQzyJRH3+O56BA7QLPZ6J1bCH+sKh4fFD7Qx8k45+kgtu8rCycJI9kUHEW/o02DUR/MYPt2PIlqxdPhnYsj4j8vvenhSrFCZtAdqq1I4Pl2RgnMAp/NdnuhWsGkUAN7UPD5A5jtti3l+e/EDeJ3ehEBsy0BTWbjprK84X7BQ3yFmDiAEtV6zSVF7SRhpIjFYTobsR+A8tFHH6Hm2KNgUahjA8OYFKofnfmL5O7V5nouleZPZ4r1LeVaNZNCZVGo97SqMo2KTaXh/HOBqvG6soFHpQUwWAdqyntzBUN8hVRSl4cAjPf0hbO4dDL55ejkiUHh/gymgMaQG3QFqkaD1cKn0at06mvN9Yh8Pnav8LeM35G16fjsQ2M0mYwcKjWCzeNSaP/sPWCKMNK1XwOzbsrDZGZm5ubmYtUNdBJityuOIMTAEd4iBoPBEAjw/mbMW8QwGo1KpRJrL5zgLWKQyWQGo1OPwRjiLWLYbDajEe/vjL1FDBqNxuG4lUvCA3iLGGazWavVYu2FE7xFDAaD4eeH902F3iKG0WhsamrC2gsneIsY3QJvEYNCoTCZeF878RYxrFarwWDA2gsneIsYVCqVxWJh7YUTvEUMi8Wi1+ux9sIJ3iJGt8BbxKDT6Xw+H2svnOAtYphMpo7ixvGDt4jRLfAWMRgMhr+/P9ZeOMFbxDAajQoFKtvCEMRbxOgWeIsYTCYzIMATm53cwVvEMBgMjY2NWHvhBG8Ro1vgLWIQoTo4ggjVIega3iIGETeFI4i4KRxBp9OJARwvmEwmYgAn6ALeIgaVSmWzH5WhHw94ixgWi0Wn02HthRO8RQwmk0mEd+IFg8FAhHfiBaJl4AiiZeAIKpXK4/Gw9sIJPXxT/qxZs6xWq81m0+v1ZrNZIBDYbDadTnfmzBmsXWuHHp73qV+/focPH25NPa/Vam02W3w8WunZ3aSHd1NLliwRiURtr7BYrPnz52Pn0aPo4WJER0cPGvQ/B/aEh4c/+eST2Hn0KHq4GI7GERh4PxE8nU5fuHAh1h51SM8XIyYmZtiw+3l98dwsvEIMAFi0aFFQUBDOmwVms6kWi7lMq9SY0Trn5EH4zF5TJ4rFYsHwQRcaZZ6pk06hRLP5QYwubJfy9HOGHSD97rWbSnkCz9eMzpFxOEFAZ9xWKaLZ/OUx/cI7yAP/AB4Vw2Czvpp/flRAaO/2jvLokSjNpj3Skn8nPxbCdJ4sw6NivHzr3CRhRGfc6mF8UnL9wNApTpN5em4APyOvDmfzvFAJAJgpitlZVeT0Ns+JUapp5lC6lue1x+BLYxSonO8O8ZwYSrPJj473ndgo4U9nWO3OZyueE0NntVh79PTpEdjs9kaT8xA6r3jo6y4QYuAIQgwcQYiBIwgxcAQhBo4gxMARhBg4ghADRxBi4IgeHjeFBjqtpiDnos1qeSwN4eV0omV0maIbV7a+/3re5fOIWybEwBGEGDgC12OGxWLJ/Pm780cylI0NfoHBI6c+NW3x/1Gp1Oxjh75LXy2K7LXu5z9odEaDTLpm0VMWqyV95+/S8tJvPngzMjbBYrU0SKt8AgKHT5w668UVNBodAKTlpf/57F/V4jKLxRIW3Xva4peGjpsEAJWlRe8vmTXp2SW1EvG9gjw6kzl49Phnl61i/ncbYE1l+d6tXxTfvEqh0AJFYSj9vfhtGXa7fcua1zO+32w06GOS+uu0LRnfb/42fTUAjJoyM2XkOFlVxaGfdlgslu0frtLrNAtfezesV6yjrKTsbmhkr4EjxmpVqsyfv/vh0zWO62wer14mjYxLCIvuXVlSuPX9NyqK7rTWeOK3XfXVkqHjJzGYzNMZe/dsXu+4XlctWft/8/MuZTHZnJCIqOqKUpT+ZPy2jNzsM7nZpyPjEj/YsZvBYuu0mg+en3PlryNTFzwfFZf4/NtrS/Jzj/zyvVxWfe9OXuqYtPFPPdNadsSkGS9/sB4A6muk78x/8tKJzLmvvOEvFPkHhWw7eolEIgHA8d9+2vP1+qtnj/dKTHaUEoZHrvvpIIPFViubXps+5sKxP55b9SGFQtm/faOuRfX4pGkvvfcplUa7cOzwt+nvoPEn41eMmxfOAgCTzc74fovjCoPBAoCKottRcYmCgMAl/3x/20erLp/M9BeGvPheetuyZOr9v0sYGt6n36DCG5fLi277C0Umg/7UgT0XT2Y2ymrsYAOAhhppaym+rz+DxQYAvsAvQBRaWyVultf5C0X5V84DwNMvv06l0QCAxUFrCzN+xVAqGgCgJO9GSd6Nttdp/z0oeci4Sbs3r1c3KcZMm8PhdRiIxRMIAEDXogaAr9e8ln85OyAkNHXcE+pmRd6lLKOh/f3INDoDAKxmi0GnMer1ZAolIDgU6T/xQfArBpvLA4B/vL22bf/TlowftqibFADw5y/fDx4zMTwmrt3bFPW1AMDm8etrpPmXs/0Cgz/fk8lgsUvyb+RdynIaNsbi8OhMpslgUDUpfPzQTcaK3wE8fsAQADi5b5e6+f7GyNL83NZvSwtuHt39A1/g+/Qrb5iNhs1rXtO3OVLJ/N/V/4KrF+/dvkUmk2OTBxp0GgDw8b/fF90ruAUAVqvzGInI2AQAOPDd1xaLBQBMqB39gN+WMXLKjFMHdtdUlv9zzoSw6Fh1c1ODTJr+U0Z0nyS9Vrtj7Ts2m23xmx8MmzBZcq/46pkT/1n/rxXpGx1lL5/MlJaXWsym2ioxAKTNXeQbGMTh83m+fuK7heuWL6ZSaXeuXwaAekml08Yx68UVn7/2wrnD+3MvnPEXBkvL0JpN4bdlMFjsNdt/GTtjLp3Jqii+bTDohk2YwuHxAWDP5vUNMumgUROGTZgMAC+s/jhQFJZz+tipA786yvoHizRKpVxWHRIZveDV1QteXQ0AdAbzjc+/iUnsV1ZYUF8teWH1x489MU2n1VSXO/lx+w55fEX6xtBesboWta6lpf/wUSj9yZ6Ltf1X8dVoFi+Rj+7O+Cunjn7zwZujp8156b1PUK2oS+is5i0Vd/4YOvnRt+G3ZXghhBg4Ar8DuGsMnzh1+MSpWHvhIkTLwBGEGDiCEANHEGLgCEIMHEGIgSMIMXAEIQaOIMTAEYQYOMJzYgTQmGQyyWPV4QobQAzbebpKz4kRzGRX6zQeqw5XyPRaKtn5T+05MVJ9hSqLyWPV4Yp6o25UgPN4Bs+J0YvDH+orPCgr91iNOOGiQma0WqcII53e6el8U5l14jMN1XFcgYjFpffwIYRUo9c0m01ai2ltwtBOFfB8kuHb6qYT9ZUKk6FGr+3E7e2gUql4PB65E72wm8gb5XQancfnkUldriuaw6ORKEP9gtOCwjtZpPtlfN6wYUNYWNizzz7rgbqWLl16/fr10NDQ2bNnL168GO3qutlzRk5Ojlgs9owSACASiex2e01Nzfbt2+fOnXvo0CFUq+tmLWPYsGEXL16kUj20Wrxv374NGza0/kRcLjc8PPyFF14YM2YMGtV1p5axYcOGDRs2eEwJR8vgcv/O9ajRaIqKitavX49Sdd1GjMOHD+t0uhEjRniyUqFQyGQy214JCgo6ceIEStV1j+iQ5ubm48eP79ixw8P1ikSi1oZot9tDQkKOHDmCXnXdo2W88cYby5cv93y9XC7Xce4lh8PJzc1NTU01mVB8idANBvD9+/fr9folS5ZgUvuqVavy8/P/+usvT1RmxzdSqXTGjBlYe/E3mZmZOTk5KBnHuxhvvfVWaWkp1l78D6NHj1ar1WhYxvWYsXv37tDQ0NjYWKwd+R9OnDhhRielPn5nU01NTbt27Tp16hTWjjwIk8msrq4mk8mIn2mN35bxzTfffPrpp1h70T4cDgeNozhwKkZWVpZSqUxNTcXakfYJCQl5++23b926haxZnE5t09LS9u7d6++P7u5SvIHHlvHjjz/OmTMH/0qcOHEiOzsbSYtoTNHcQa/XP/7441h70SlUKtWYMWMQNIi7burLL7+MjY2dPn061o50Cr1eT6FQ6HQ6Itbw1U3V1dWdPXu2uyjhmObakDv6AF9i/PDDDy+99BLWXnQBEom0dOnSgoICRKzhSAy5XC4Wi2fOnIm1I11j9uzZSK1w4GjM2LRpU0BAAM7PNUQVHInh4fVtBCkpKQkICHB/Lo6XburIkSOLFy/ujkoAQHl5+aZNm9y3gxcxDh06NHz4cKy9cJG0tDQ/PwRyouCim5LL5YsWLUJvob+7gIuWcenSpblz52LthVvk5+fn5eW5aQQXYpw9e7ZPnz5Ye+EWFotl27ZtbhrBhRjXrl0bOrRTcdq4ZdCgQb169XLTCPZiFBQUTJgwoZvOo9qyevVqNy1gL0ZRUZGPT084kTo7O7uwsNAdC9iLIRaLk5OTsfYCARoaGjIzM92xgL0YxcXFERERWHuBAOPGjXv88cfdsYC9GBKJJDLS+X43/OPn5zdy5Eh3LGAshlKpTEpKaht2361Zv369wY0UxBiL0dTU1NDQgK0PCHL79u3KykqXi2Mshkql6t+/P7Y+IMjKlSt5POeZEDoC49m9SqVSKpXY+oAgw4YNc6c4xi3DbDb3jKmUgzt37ly+fNnl4hiLodFo1Go1tj4giEwmc+dRA+NuikwmBwYGYusDggwcOJBGo7lcHJv1jJkzZxqNRqvVajQabTYbl8u1Wq1ms/ncuXOedwY/YNNNRUZGyuXypqYmrVar1+sdn3tAE9FqtV988YXLxbERY+HChQ8s3zOZTI/lPUAPJpP5+++/u1wcGzFSU1MTEhLa9pAhISGzZs3CxBkEoVAo69atc5wG5AKYzabmzZvX2i/R6fRnnmn/lKtux8SJE11em8FMjKFDh8bFxTkaR0RERA9oFg62b99eX1/vWlksnzPmz5/v4+NDp9PnzJnjgeRRnuHGjRu1tbWulXXeoOwARpu1yYT8eWgRA/pGpfRXKpXDp06SGVxMBPYI2FSagIpMsH7nWbRokVAodK2sk+eMI3WVf8jK5UY9h+r6swxWMMkUrdUyJTjyuYgErH3pFI8S40dJ8d2W5jEBob40hme9QgyVxZSvbNRbLR8mDPFMjadOnQoNDU1MTHShbIc99Y9VxRUa9VMhvbqvEgDgQ6WPChAJ6IyPiq95psYbN24UFRW5VrZ9MSR6TYmmeWpwT1gNBYChvkIyiXRN6YlVrOnTp6ekpLhWtv0BXKxVWeyI7Y7CA1QS6a66aYggCO2KkpKSXC7bfsuoN+pDmT1kXdpBCJPTbEbrgNy2nDp16uTJk66VbV8Mo9VisFnd8wpfWOw2FTrZVx6gpqbm3r17rpXt9kGVeCMtLc3lbG2EGAgjEolcLttDXkLgh/Pnz+/bt8+1soQYCNPY2Fhe7uJJCEQ3hTCjR48eNGiQa2UJMRAmICAgICDAtbJEN4UwOTk5P//8s2tlCTEQRqFQlJWVuVaW6KYQxrGC6VpZQgyEIcYMHJGXl/fLL7+4VpYQA2EaGhqKi4tdK0t0UwjTt29fl0MjCTEQJiQkJCQkxLWyiIlxOmPv8d9+VDTU+wcJRz05e8aSlx3Xb5w/fXzvj1X3iskUWu+kvnOX/jMqLtFutx/9dee5Q/sU9bU+vgHD0qbOeWkljc4AgK/eWZ6bfWbi7AVFuTn1NZL4AamrN+8EgJwzJzJ3fSurLGdyuQMfH/vssjf5vggkskGcwsLCkpIS18LAkBkz7ly//NOGtaqmxgHDRzHZXEW9zHH9xL5dm1avKC24GRweHRgsKsi52KJsBoDdX3/229Yv1M3N8QNSzRbT0d0/bP3Xm20NnsrY4xsoTBk5fvysZx12tr7/ukwi7pXYl8XiZB/JSF+6QK9FPrrHfWpqam7cuOFaWWRahrS8FACGjJ30f+9/CgAGnQ4AlI3yfd98SSKR3vn6P8mpjwFATWV5aFRMg0z61/5f6EzmJ7sOCkPDW5TNqxdOy80+XVaY3zvp/v6+YRMmr0j/yvFZpWjc982XTDYnfeeBkMhou92+fe3bl09mZmX+PvnZ5xDxH0H69OnD4XBcK4uMGH2HjqBQqRdPHKYzGZPnPS8MDQeAgmuXzGZTv2EjHEoAQGhUDAAUXr9it9sHDB/tuI0n8E0ZOe7cof0lt663FaPVeP7Vi2azSRAYdO7wfscVvVYDABXFdxBxHlkiIyNd3taOjBhh0b3f3vj9jxvWns7Ye/bQ/lkvrJj5j6WqRjkABIU+uGWvRakEAIH/31MOH4EfAGhaVK1XmOy/V+AdduSy6mN7f2xrh874n3PCcEJZWVlFRUVaWpoLZREbwJNSh3/+69ELx/74aUP6ge++7j98JJvHB4Bm+YMBMjyBAADUSkXrlaZGOQBwfXzbtczm8gBg2IQpK9I3IuUtelRUVGRlZbkmBmIPfXXVEgqFMmbanL5DHgOA+mpJ/MDBAJB3Oav09v2jDcQlhSajITFlKADkXc5WNNQCQJO87kbWKQBIHNR+yqn4lFQAyL1wtrzodqsdo16HlOfIEh0dPWrUKNfKItMy6qolbz8zKSZ5AF/gW5BzgUpnxCT2CxSFjXpydvaRjE9eWRDaK5ZEIlWXlz636sNxM58ZM/3prD9/f3fhzKg+CZUlxTqNetiEKdF92o84Co2KGTl55oXjh9a+9ExEbILFYpaJy+atfBuHozcAxMbGunwuETJiWC3mpNThJfm5JBIpKi7x6VdeDxSFAcALqz8OCY/KOnJAVlnOZHPiU4aG9YoFgOdWfegXJMw++kdJ3g2BX+D4p56Z9eKKR9h/cc264Mio7CMHJWV3GQxWfMqQyN7xiHiOOFVVVdXV1a6l12k/8PkXyd1qg3ZsQCgS7uGC22pFrUH3QTzqR9X89ddfWVlZrh1QRLwoRJjQ0NDBgwe7VpZ4N4UwSUlJLofbEi0DYWQyWX5+vmtlCTEQ5tatWxkZGa6VJcRAmJCQkH79+rlWlhgzECYlJcXlzTJEy0AYmUxGLLvihStXrpSUlCQkuLK/lhADYUQiEYVCca0sIQbCuHMkCzFmIExlZWVJSYlrZYmWgTDnzp3TarWuHQdCiIEwUVFRLmcabF8MNpXGILs4CuETKonsR/dEqoexY8e6XLb9MUPIYFfrW9xwCXfI9Fp/uifWzPPz813eEtC+GHE8AZXUo1qGBezxPE8EvR05csTlo17bFyOIzhriK8yQubhREG+ckVfzqNSBPi5G6neJQYMGuZZSx0mKo+P1VSfrJSP8Q4RMNo3U/SbBNoBag7aopSmQznoluhscXuMk+de15vqMmrK7GiWCp163xWa32+12Cjo58QR0Bo9Knxoc7cn0QEeOHOnfv394eLgLZZ1MbYf4Cof4CgFAb3UxPeijOXjwoEQief3119EwzqRQSWjYfSQHDx4MDw9HRYxWWBRUnkhodqBYbSgZx4Rx48aFhroYyNFzfgWc4M555hgPy0wms8ccuOTg4MGD3S/jswODwaDRaLD1AUHMZvO///3v7pfx2QGLxRIIBNj6gCBGo3Hx4sUuF8dYDKPRqFAoOnFj94DL5S5btszl4hiLweFwesbBrg5qa2vPnDnjcnGMxSCTydXV1dj6gCC5ubkXLlxwuTjGU1sul4vJOUMoER4eHhwc7HJxjMVgs9lyuRxbHxDEzQMgMe6meDxeS0vPWTg5duxYVVWVy8UxFoPP57v88gCH7Ny5051eF2MxgoKCsrOze8ywMW7cOHcO5MR+lSI4ONjlc3HwxrJly9w5Igd7Mfr3798zxKiurj59+rQ7FrAXg81mu5wIFlecOnXq7t277ljA/hV6VFSUOwea44eoqCiXE1U4wF6MuLg4l/dd4Qp3IqYcYN9NJScnu3OGNk7Q6/Wff/65m0awF4PFYoWGhroc+IUTCgoK3J+gYy+GIxdsXl4e1l64hb+//7x589w0ggsxhgwZ4s7LTjzQu3dvN0dvvIgxYsSIS5cuYe2F62g0mo8//th9O7gQw/EiwZ1lGWw5ffo0iYRAiBZexJg6derRo0ex9sJFEhMTV65c6b4dvIgxevRosVisxWVCTqfExcUhElaBFzEAYPz48fv378faiy5z6tSpLVu2IGIKR2IsXLhw9+7dWHvRZU6ePDlmzBhETDmJQvcwmzZtSkpKmjhxItaOYAOOWgYAPP3000g1ec+gVCoRXDbGlxihoaGDBg36888/sXaks0yYMAHBWGF8iQEAy5cv7y4PHOfOnVuzZg0iTxgO8DVmONi8ebOPj8+SJUuwdsTT4FEMAJg2bdrBgwdpNBrWjnRIUVGRXC4fPXo0gjZx1005ePnll9etW4e1F4/itdde69u3L7I2cSrGk08+WVNTc/PmTawdaR+lUrlnzx4/P4Q3luO0m3KkNEtPT9++fTvWjngOnLYMRxatwYMHb9u2DWtHHmTr1q0HDhxAwzJ+xQCAF154QSwWV1RUYO3I39TW1spksjlz5qBhHL/dlAOpVLpy5cpDhw5h7YgnwHXLcOx4mD9/fmtnNWPGjKeeegorZ3JyclB9O4B3MQBg7ty5jY2Nubm5o0aNqqmpMZlMEonE826oVKr33ntv+vTp6FWBfRBbZ8jPzz98+LDjxYPRaKytrXUn2Ns1tFot2muR3UCMJ554QqFQtL4C0ul0dXV1Hvahvr7eZrOxWCxUa8F7NzVmzJjGxsa2V4xGo1Qq9aQPUql0w4YNYWFhaFeEdzGysrImTpzo6+vbdtbncq5S12hsbExPT/dARXif2jooLi7esWPHnTt3mpubyWRyVFQUSo9dD6PVaikUCpN7P7y3AAANyklEQVTpifyGeG8ZDhISEr7++uv169enpKT4+PiYzWaVStWJcu5y7dq1t956yzNK4KJl3NOqfpWW3NMoVSZjZ+632qwWi5VBp6PvGpgtFiq1sxnEojh8JoU6MSgiLciVzF/Yi3G5qe57ceHowNAgBovbzVOAWey2Gr22TKsKZnKWupQSEUsxTjZIjtSKF4S7kqkaz/zVIGVTqG/FDuxqQczGDLXFfLyuqucpAQBpQeFaq/la84OH2joFMzGK1Ao7dIOJnGtwKLSbyu4jRo1BG8niYVU72oSxOCpLp+YjbcFMDJ3FbLSjkisXF9ihztDlc5m7x3OGl0CIgSMIMXAEIQaOIMTAEYQYOIIQA0cQYuAIQgwcQYiBIwgxcAQhBo4gxMARhBg4ghADR3SbGABlo3zFtJE8gSCid2Lp7ZssFit56Ihnl7/pFxgMAF+9szw3+8zE2QuKcnPqayTxA1JXb97puLh6887k1McA4ObFcxtXLR02YfKK9K+O//bTnq/XL3z93Usn/5RVVggCgp54emHa04taq8s5cyJz17eyynImlzvw8bHPLnuT74v6aaTdrGW0KJUWs3HouDQ6i335ZOa65UtMBn3rt6cy9vgGClNGjh8/69nOWNu96TMGkz103GR1U9PPG9ddPpnpuH5i366t778uk4h7JfZlsTjZRzLSly7Qo5/xp9u0DAcBIaH/2rEHAExGw4cvPiMtK7l27q8Rk2c4vnX8r++8tceemLbsoy8AYPCYiRtXLc06cvCxJ6apFI37vvmSyeak7zwQEhltt9u3r3378snMrMzfJz/7HGp/GXQ/MVozjdMZzKHjJ0vLSsoLC9qK0SVrgcEix4de8ckAIJdJASD/6kWz2SQIDDp3+H6+Jb1WAwDlRbcR/VPaoZuJ0Raejy8A6LTq1itMtotpPGgMOgBYTGYAUDXKAUAuqz6298e299AZqAd5dmMxFHU1AMDm8Du+hQQAXT0imM3lAcCwCVNWpG9038ku0c0GcKvF4vhx5bU12ccOAUCfgakd3cz38wMA8d07AGCxWK6dPdGZKuJTUgEg98LZ1n5JXFJo1Hc51MMFulnLUNTXvjF7ApfnU1NVYTEZoxOSB4+e0NHN/YaOOHdo/4Fvv76ZfVbRUKds7FRUWWhUzMjJMy8cP7T2pWciYhMsFrNMXDZv5dtoj97dr2Uw2RwWi11TWcbl+0yYPf/dzTsfcXZn6pi02S+u9A0QSspLQ6N6T1v8UidreXHNuqdfeT1QFCYpu6uolcWnDInsHY/cH9EhmAU+/yK5W23Qjg3o7IFLjoe+oNDwjQdOoewaAlRq1VeV9V/1HdmlUt2sZfRsCDFwRLcZwAUBgbuvuHWIDv4hWgaOIMTAEYQYOIIQA0cQYuAIQgwcQYiBIwgxcAQhBo7ATAwGhUon9dj/CmQy2Y/e5ZVBzH4OfzqzweiJFRtMaDDqOJQuJ3LHTIwoNh/Bww7whtZqSeR3Oc4KMzFiOHwRk3teIcPKAfSQ6DXlGtWkoC6ntMSy1341ph8FSCcbJKYuxgzgFjvAHXXTyfqqrf1dOcoB++Rfv1XfO1wrJoGdT0XxtAyL1Wq1opsyjEtj3FY1Tg6Oej2mv2sWsBcDAGwAdQZtk8mAXhWXLl0qKSl5/vnn0auCRaXGsH3csYCLxSUygIjJETE56FWh8Q1i+SmT+f7oVeE+uGgZBA567GPXAzQ2NorFYqy9cIK3iHHlypVdu3Zh7YUTcDFmeIBevXo9ItwNJxBjBo7wlm6qsbERV8cFtYu3iHHlypWff/4Zay+cgPduFCnCw8MtFgvWXjiBGDNwhLd0U7W1tUVFRVh74QRvEePGjRv79+/H2gsneMuYIRKJ9Hp9J27EEmLMwBHe0k1VV1ffunULay+c4C1i3Lp16/Dhw1h74QRvGTOI5wyCruEt3ZRMJrt9G/XkH27iLWLk5uZmZGRg7YUTvEWM4ODgPn3wfr4TMWbgCG9pGXK5/N69e1h74QRvEePatWv4fzflLWKw2WwfH7cizDwAMWbgCG9pGRaLxWQyYe2FE7xFjOPHj3/66adYe+EEbxGDTCa3Zv7ELcSYgSPw/p8FKYgxA0cQYwaO4PP5QUFBWHvhBGLMwBHe0jLUanVdXR3WXjjBW8Q4f/78jh07sPbCCd4iBjFmEHQNb2kZLS0tDQ2dyoWOId4iRlZW1rZt27D2wgneIoaPj09wcDDWXjihh48Z06dPl8lkrUeaON4V+vv7nzx5EmvX2qGHt4x//OMfdDq97Vtbu90+ZMgQrP1qnx4uxlNPPRUa+j+nQoSEhCxevBg7jx5FDxcDAObNm0f/bzIdu92ekpISGxuLtVPt0/PFmDVrVmvjEAqFuG0WXiGGo3EwGAzHaNG7d2+s3ekQrxBj1qxZYWFhQqFwwYIFWPvyKPC4PyNXKbfZ7TEc/mm5tECtkBt0AwVBw/2Cb6oachR1rn2O+MfcErvhDNWoUzW6Y+emquGuRpniEzg2IKxE00whkVIEQUwyBZE/HEfPGVW6FiqZ/K34TnFLk9JscmT2tJOA9F8HcfIZ7EACEoAdANhUajzXd0F4HxKJlMxz91hkXIhhttveLbxSb9DWG/G+IbUjfGh0XxpjY79RXIrrnQ32YlxpqvuturS4pRlbNxAhjMWdE9p7kjDStaEYYzE+unutQKXQWPAet9F5aCRyCJOzY+BYatdTKGM5m/pVWnq9uaEnKeHociX6lrXFV10oi5kYFVrVnuoSs82KlQOocrW5fo+0tKulsOmmtlbcPiuXaixmz1ftMcgkUl++/xfJj3ehCJr+tE+ZVnVL2dCzlQAAm90u0bXkKruwvIiBGM0mo1Sv8Xy9nqfZbLynUXX+fk+LcUfdtLEM7zk8EGSPtORb8Z1O3uxpMbZU5CvQzHnuJllTF5X/Zy+CBo0264n6KrW1UzNGj4qhsZp9qAxP1tgl9HUNZlULJzocWbNsKo1B6tTLK4+KwSBRSjX4fdJuKRUDADc6ElmzcqO+oXOveTz61va7ykKdFa3UNjaTuXLvH7Unsgz1ckaAX+S8meFPTQaA/DWf03x4Pgmxlb/+Yahv5MVG9/3wnyyREADsVqtkf2b1n38Z6uX8xDhuVDiJSmWHixD3bWX++UPDpjq9zaMto1DdhJJlm9l888214l0HAkcMSXp3pU9y/N0vv20prwIAk0pddyq75tiZ6MVzIufNUBWWiH854Ch1J31T6faffQckJb67kspiVh86wYkQkanIvA9vC41Eru3EaV8ebRkDBQFlWiUalsW/ZDTfutP/s3eDRg4FAJYouO6v80a5ghcTadXpebHRgzZ/4viV685c1NfWA0Dd6Qt1py/EvfpC5NxpACAcMzxryiJOL4T7KAeD/YKEDJbT2zw7ZiC0CPMAdrtdevA4MziIFxNlbGxSXM+7+9V3dF8fQb8Eu82mldT4Dkhq/f9u0xtofB4ASDOOsUTC8FlT7huxWK0GIze6y6dWdYYGgx7A+XtDz7UMk812or4KDcuG2gazUmVjsy7OfdlxxXdgcsqmj6lslq6m1mYwcqLuT5AsOr1R0cyOCLVZLKrie8ETR7WKpK2qBrsdJTEkek2eSp7iE/jo2zwnBp1MtqLzGsxmsQBAn5XP+w5IMqs1zJAghp/A8ZVGLAWA1p9YI5Y4/mlp0dgtFoa/b6uR5rxCAOD2QkUMGonkQ3V+9pZHu6mXo5PRMMsUBgCJpC6tYIeLfJLiWpUAAK1YAmQyO+J+qI62QgIAnKhwKo9LopB1NbWO61aDUZJxlMygO2ZZiDMuMDyG4zxziUcH8P4+7q4StwuFwQgaM7zmz5MkCpkf31tTXuWT3Ec4erijZbBEQgrj/v9KjVhCopA5ESIyleo/NEWenVOxaz8nPLRq/5/GhkZu72gSOhv3A5nOR29Pi5GnUvjRGE1mI+KWE1ctLaHT6s9clB09w42OCJk01nFdK5Zwo/5+otaIpSxRMJlGA4DEd5YXb9hR9eshMpMRNuMJs6oFpQGDTCLda1FCJ0LgPbqeobKYX7x5WmXuUUt7Tgmgs96KHZgicDJ6Y7C4dKel6Z8FFx5xQ/EX2+vOXHz4OiPI39igePg6jc8bsR/JnZPXl72rqZA8fJ0X16ultP2zaUYd3klhdPjO7dWY/k8GR3Wmak+LYbLZNpXnnW6QdniDUm3Vt/Na12Y2O7qXByCRyUxhAIIeGhqb7Ob23tncD5VqB2ZwYEcnOItYnLUJQyNZvM5U7emIQjqZDAAUEsnawX8CuoAPAr6HvWoLMwDJWQaHQuukEtis9L3Re0Ci28F33YJ4nu+H8V3YmINZ3NRHxVcvN+E9ZYE7CBms7QPGcrtylDNmoTqP+YtYFFReVeEBEomUIgjqkhIYRxRmyWt2V5dIdC1YOYASPCptmG/wqriUrhbEOLyzzqD7qjzvllKOoQ/IIqAxtvQbJWSyXSiLfeCz2W576/YlldkoM2ix9cRNhAy2Dezv90lN4Pl24vZ2wF4MB0UtTQar9fvKQqleY+puMZ8BDNZsUcwkYQSH0rVB4gHwIoaDexrlabmUTaGZbdbLTXVKs7E18NBuh9bnKsw/sylUBpk6yDewv0/ATaV8kCAwLQiB91r4EqMt97QqqU7T38ffn868qJA1mgwj/UU4+XylqY5MIqUIAmkkJKej+BXDC/GK3a7dBUIMHEGIgSMIMXAEIQaOIMTAEf8PwwP2AAo2/7wAAAAASUVORK5CYII=",
      "text/plain": [
       "<IPython.core.display.Image object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from langchain_opentutorial.graphs import visualize_graph\n",
    "\n",
    "visualize_graph(create_graph())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9116269c",
   "metadata": {},
   "source": [
    "## Run Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0922dbdf",
   "metadata": {},
   "source": [
    "Generate the number puzzles that fit a range using the Number Combination Puzzle Generator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "a253424f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Example puzzles: ['3 4 6 9', '1 4 7 8', '1 2 5 8']\n"
     ]
    }
   ],
   "source": [
    "import itertools\n",
    "import random\n",
    "\n",
    "def generate_make_puzzles(count=10, seed=None):\n",
    "    if seed is not None:\n",
    "        random.seed(seed)\n",
    "    \n",
    "    numbers = list(range(1, 10))\n",
    "    all_combinations = list(itertools.combinations(numbers, 4))\n",
    "    selected_combinations = random.sample(all_combinations, min(count, len(all_combinations)))\n",
    "    \n",
    "    return [\" \".join(map(str, combo)) for combo in selected_combinations]\n",
    "\n",
    "# Example of generated number puzzles\n",
    "puzzles = generate_make_puzzles()\n",
    "print(f\"Example puzzles: {puzzles[:3]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c45ed7be",
   "metadata": {},
   "source": [
    "Find the equation to reach the number 15 by combining the numbers in the given puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "6669d210",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "New puzzle: 2 5 6 7\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[6.0, 5.0, 2.0, 7.0, '*', '-', '+']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, 2.0, 5.0, '*', 6.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, 6.0, 7.0, '-', 2.0, '*']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, 7.0, '+', 2.0, '*', '-']), score=None, feedback=None)]}}\n",
      "Step: {'score': {'scored_candidates': [ScoredCandidate(candidate=Equation(tokens=[6.0, 5.0, 2.0, 7.0, '*', '-', '+']), score=0.0, feedback='Result: -3.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, 5.0, '*', 6.0, '-']), score=0.4666666666666667, feedback='Result: 7.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0]), score=0.6, feedback='Result: 9.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 6.0, 7.0, '-', 2.0, '*']), score=0.33333333333333337, feedback='Result: 5.0'), ScoredCandidate(candidate=Equation(tokens=[6.0, 7.0, '+', 2.0, '*', '-']), score=0, feedback='The equation must use all 4 numbers exactly once.')], 'candidates': 'clear'}}\n",
      "Step: {'prune': {'candidates': [ScoredCandidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0]), score=0.6, feedback='Result: 9.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, 5.0, '*', 6.0, '-']), score=0.4666666666666667, feedback='Result: 7.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 6.0, 7.0, '-', 2.0, '*']), score=0.33333333333333337, feedback='Result: 5.0')], 'scored_candidates': 'clear', 'depth': 1}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[7.0, '-', 5.0, 2.0, '*', '+', '*', 6.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, '*', 5.0, '+', 6.0, '-', 7.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, '+', 5.0, '*', 2.0, '-', 7.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, '+', 7.0, '*', 5.0, '-', 6.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '+', 6.0, '-', 2.0, '*', 7.0]), score=None, feedback=None)]}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[6.0, 2.0, 5.0, 7.0, '*', '+', '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, 6.0, 2.0, '*', 7.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, 5.0, 6.0, 2.0, '*', '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, 6.0, 5.0, 7.0, '*', '+']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, 5.0, 7.0, 6.0, '*', '-']), score=None, feedback=None)]}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 7.0, '*', '-', '-', 5.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '*', 6.0, '-', 7.0, '+', 2.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, '*', 7.0, '+', 6.0, '-', 5.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 6.0, '-', 5.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, '+', 5.0, '+', '-', '-', 7.0, '+', 2.0]), score=None, feedback=None)]}}\n",
      "Step: {'score': {'scored_candidates': [ScoredCandidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0]), score=0.6, feedback='Result: 9.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, 5.0, '*', 6.0, '-']), score=0.4666666666666667, feedback='Result: 7.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 6.0, 7.0, '-', 2.0, '*']), score=0.33333333333333337, feedback='Result: 5.0'), ScoredCandidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 7.0, '*', '-', '-', 5.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[5.0, '*', 6.0, '-', 7.0, '+', 2.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[2.0, '*', 7.0, '+', 6.0, '-', 5.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 6.0, '-', 5.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[6.0, '+', 5.0, '+', '-', '-', 7.0, '+', 2.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[6.0, 2.0, 5.0, 7.0, '*', '+', '-']), score=0.0, feedback='Result: -31.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 6.0, 2.0, '*', 7.0, '-']), score=0.33333333333333337, feedback='Result: 5.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 5.0, 6.0, 2.0, '*', '-']), score=0.4666666666666667, feedback='Result: 7.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 6.0, 5.0, 7.0, '*', '+']), score=0.1333333333333333, feedback='Result: 2.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 5.0, 7.0, 6.0, '*', '-']), score=0.1333333333333333, feedback='Result: 2.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, '-', 5.0, 2.0, '*', '+', '*', 6.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[2.0, '*', 5.0, '+', 6.0, '-', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[6.0, '+', 5.0, '*', 2.0, '-', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[2.0, '+', 7.0, '*', 5.0, '-', 6.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[5.0, '+', 6.0, '-', 2.0, '*', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\")], 'candidates': 'clear'}}\n",
      "Step: {'prune': {'candidates': [ScoredCandidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0]), score=0.6, feedback='Result: 9.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, 5.0, '*', 6.0, '-']), score=0.4666666666666667, feedback='Result: 7.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 5.0, 6.0, 2.0, '*', '-']), score=0.4666666666666667, feedback='Result: 7.0')], 'scored_candidates': 'clear', 'depth': 1}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 5.0, '-', 7.0]), score=None, feedback=None)]}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[5.0, 7.0, '*', 2.0, '-', 6.0, '+']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, 6.0, '*', 5.0, '/', 7.0, '+']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, 2.0, '*', 6.0, '-', 5.0, '+']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, 7.0, '+', 5.0, '-', 2.0, '/']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, 5.0, '*', 7.0, '/', 6.0, '+']), score=None, feedback=None)]}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 7.0, '-', '+', 5.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '+', 7.0, '*', 2.0, '-', '/', '+', 6.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 5.0, '-', 6.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 5.0, '/', 7.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '*', 2.0, '+', 6.0, '-', 7.0]), score=None, feedback=None)]}}\n",
      "Step: {'score': {'scored_candidates': [ScoredCandidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0]), score=0.6, feedback='Result: 9.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, 5.0, '*', 6.0, '-']), score=0.4666666666666667, feedback='Result: 7.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 5.0, 6.0, 2.0, '*', '-']), score=0.4666666666666667, feedback='Result: 7.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 7.0, '*', 2.0, '-', 6.0, '+']), score=0.0, feedback='Result: 39.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 6.0, '*', 5.0, '/', 7.0, '+']), score=0.6266666666666667, feedback='Result: 9.4'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 6.0, '-', 5.0, '+']), score=0.8666666666666667, feedback='Result: 13.0'), ScoredCandidate(candidate=Equation(tokens=[6.0, 7.0, '+', 5.0, '-', 2.0, '/']), score=0.2666666666666667, feedback='Result: 4.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 5.0, '*', 7.0, '/', 6.0, '+']), score=0.49523809523809526, feedback='Result: 7.428571428571429'), ScoredCandidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 5.0, '-', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 7.0, '-', '+', 5.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[5.0, '+', 7.0, '*', 2.0, '-', '/', '+', 6.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 5.0, '-', 6.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 5.0, '/', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[5.0, '*', 2.0, '+', 6.0, '-', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\")], 'candidates': 'clear'}}\n",
      "Step: {'prune': {'candidates': [ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 6.0, '-', 5.0, '+']), score=0.8666666666666667, feedback='Result: 13.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 6.0, '*', 5.0, '/', 7.0, '+']), score=0.6266666666666667, feedback='Result: 9.4'), ScoredCandidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0]), score=0.6, feedback='Result: 9.0')], 'scored_candidates': 'clear', 'depth': 1}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[7.0, '*', 2.0, '-', 6.0, '+', 5.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '+', 6.0, '+', 7.0, '-', 2.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, '+', 2.0, '*', 5.0, '/', 7.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, '*', 5.0, '+', 7.0, '-', 6.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '*', 2.0, '+', 6.0, '-', 7.0]), score=None, feedback=None)]}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[7.0, 2.0, '*', 6.0, '/', 5.0, '+']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, 6.0, '*', 2.0, '-', 7.0, '+']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, 2.0, '*', 7.0, '-', 5.0, '+']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, 7.0, '*', 2.0, '/', 6.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, 5.0, '-', 2.0, '+', 6.0]), score=None, feedback=None)]}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[7.0, 2.0, 5.0, '*', '+', 6.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, 6.0, '*', 2.0, '+', 7.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, 2.0, '*', 5.0, '-', 7.0, '+']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, 7.0, '*', 2.0, '/', 6.0, '+']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, 5.0, '*', 6.0, '/', 7.0, '+']), score=None, feedback=None)]}}\n",
      "Step: {'score': {'scored_candidates': [ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 6.0, '-', 5.0, '+']), score=0.8666666666666667, feedback='Result: 13.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 6.0, '*', 5.0, '/', 7.0, '+']), score=0.6266666666666667, feedback='Result: 9.4'), ScoredCandidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0]), score=0.6, feedback='Result: 9.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 6.0, '/', 5.0, '+']), score=0.48888888888888893, feedback='Result: 7.333333333333334'), ScoredCandidate(candidate=Equation(tokens=[5.0, 6.0, '*', 2.0, '-', 7.0, '+']), score=0.0, feedback='Result: 35.0'), ScoredCandidate(candidate=Equation(tokens=[6.0, 2.0, '*', 7.0, '-', 5.0, '+']), score=0.6666666666666667, feedback='Result: 10.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 7.0, '*', 2.0, '/', 6.0, '-']), score=0.7666666666666666, feedback='Result: 11.5'), ScoredCandidate(candidate=Equation(tokens=[7.0, 5.0, '-', 2.0, '+', 6.0]), score=0.2666666666666667, feedback='Result: 4.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, 5.0, '*', '+', 6.0, '-']), score=0.7333333333333334, feedback='Result: 11.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 6.0, '*', 2.0, '+', 7.0, '-']), score=0.33333333333333337, feedback='Result: 25.0'), ScoredCandidate(candidate=Equation(tokens=[6.0, 2.0, '*', 5.0, '-', 7.0, '+']), score=0.9333333333333333, feedback='Result: 14.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 7.0, '*', 2.0, '/', 6.0, '+']), score=0.43333333333333335, feedback='Result: 23.5'), ScoredCandidate(candidate=Equation(tokens=[2.0, 5.0, '*', 6.0, '/', 7.0, '+']), score=0.5777777777777777, feedback='Result: 8.666666666666666'), ScoredCandidate(candidate=Equation(tokens=[7.0, '*', 2.0, '-', 6.0, '+', 5.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[5.0, '+', 6.0, '+', 7.0, '-', 2.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[6.0, '+', 2.0, '*', 5.0, '/', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[2.0, '*', 5.0, '+', 7.0, '-', 6.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[5.0, '*', 2.0, '+', 6.0, '-', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\")], 'candidates': 'clear'}}\n",
      "Step: {'prune': {'candidates': [ScoredCandidate(candidate=Equation(tokens=[6.0, 2.0, '*', 5.0, '-', 7.0, '+']), score=0.9333333333333333, feedback='Result: 14.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 6.0, '-', 5.0, '+']), score=0.8666666666666667, feedback='Result: 13.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 7.0, '*', 2.0, '/', 6.0, '-']), score=0.7666666666666666, feedback='Result: 11.5')], 'scored_candidates': 'clear', 'depth': 1}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 6.0, '-', '*', '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, 5.0, '*', 2.0, '+', 7.0, '/', '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 6.0, '*', '-', '/']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, 2.0, '*', 7.0, '+', 6.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '*', 2.0, 2.0, '+', 7.0, '+']), score=None, feedback=None)]}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 5.0, '-', 7.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '*', 2.0, '+', 6.0, '-', 7.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, '+', 6.0, '+', 2.0, '-', 5.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '+', 7.0, '+', '*', 2.0, '-', '*', 6.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 5.0, '-', 6.0]), score=None, feedback=None)]}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[6.0, 5.0, '*', 7.0, '+', 2.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, 5.0, '*', 6.0, '+', 7.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, 2.0, '*', 6.0, '+', 7.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, 2.0, '*', 5.0, '+', 6.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, 7.0, '-', 6.0, '+', 2.0, '*']), score=None, feedback=None)]}}\n",
      "Step: {'score': {'scored_candidates': [ScoredCandidate(candidate=Equation(tokens=[6.0, 2.0, '*', 5.0, '-', 7.0, '+']), score=0.9333333333333333, feedback='Result: 14.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 6.0, '-', 5.0, '+']), score=0.8666666666666667, feedback='Result: 13.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 7.0, '*', 2.0, '/', 6.0, '-']), score=0.7666666666666666, feedback='Result: 11.5'), ScoredCandidate(candidate=Equation(tokens=[6.0, 5.0, '*', 7.0, '+', 2.0, '-']), score=0.0, feedback='Result: 35.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 5.0, '*', 6.0, '+', 7.0, '-']), score=0.6, feedback='Result: 9.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 2.0, '*', 6.0, '+', 7.0, '-']), score=0.6, feedback='Result: 9.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 5.0, '+', 6.0, '-']), score=0.8666666666666667, feedback='Result: 13.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 7.0, '-', 6.0, '+', 2.0, '*']), score=0.5333333333333333, feedback='Result: 8.0'), ScoredCandidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 5.0, '-', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[5.0, '*', 2.0, '+', 6.0, '-', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[7.0, '+', 6.0, '+', 2.0, '-', 5.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[5.0, '+', 7.0, '+', '*', 2.0, '-', '*', 6.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 5.0, '-', 6.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 6.0, '-', '*', '-']), score=0, feedback='The equation must use all 4 numbers exactly once.'), ScoredCandidate(candidate=Equation(tokens=[6.0, 5.0, '*', 2.0, '+', 7.0, '/', '-']), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 6.0, '*', '-', '/']), score=0, feedback='The equation must use all 4 numbers exactly once.'), ScoredCandidate(candidate=Equation(tokens=[5.0, 2.0, '*', 7.0, '+', 6.0, '-']), score=0.7333333333333334, feedback='Result: 11.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, '*', 2.0, 2.0, '+', 7.0, '+']), score=0, feedback='The equation must use all 4 numbers exactly once.')], 'candidates': 'clear'}}\n",
      "Step: {'prune': {'candidates': [ScoredCandidate(candidate=Equation(tokens=[6.0, 2.0, '*', 5.0, '-', 7.0, '+']), score=0.9333333333333333, feedback='Result: 14.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 6.0, '-', 5.0, '+']), score=0.8666666666666667, feedback='Result: 13.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 5.0, '+', 6.0, '-']), score=0.8666666666666667, feedback='Result: 13.0')], 'scored_candidates': 'clear', 'depth': 1}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 5.0, '-', 6.0]), score=None, feedback=None)]}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[5.0, 7.0, '+', 6.0, '*', 2.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[7.0, 5.0, '*', 6.0, '+', 2.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, 6.0, '*', 5.0, 7.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, 5.0, '+', 2.0, '*', 7.0, '-']), score=None, feedback=None), Candidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0, '+']), score=None, feedback=None)]}}\n",
      "Step: {'expand': {'candidates': [Candidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 5.0, '-', '-', 6.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 7.0, '-', 5.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '*', 2.0, '+', 6.0, '+', 7.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[6.0, '*', 5.0, '/', 2.0, '-', 7.0]), score=None, feedback=None), Candidate(candidate=Equation(tokens=[5.0, '+', 6.0, '+', 7.0, '-', 2.0]), score=None, feedback=None)]}}\n",
      "Step: {'score': {'scored_candidates': [ScoredCandidate(candidate=Equation(tokens=[6.0, 2.0, '*', 5.0, '-', 7.0, '+']), score=0.9333333333333333, feedback='Result: 14.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 6.0, '-', 5.0, '+']), score=0.8666666666666667, feedback='Result: 13.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 2.0, '*', 5.0, '+', 6.0, '-']), score=0.8666666666666667, feedback='Result: 13.0'), ScoredCandidate(candidate=Equation(tokens=[5.0, 7.0, '+', 6.0, '*', 2.0, '-']), score=0.0, feedback='Result: 70.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, 5.0, '*', 6.0, '+', 2.0, '-']), score=0.0, feedback='Result: 39.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 6.0, '*', 5.0, 7.0, '-']), score=0.8, feedback='Result: 12.0'), ScoredCandidate(candidate=Equation(tokens=[6.0, 5.0, '+', 2.0, '*', 7.0, '-']), score=1.0, feedback='Result: 15.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0, '+']), score=1.0, feedback='Result: 15.0'), ScoredCandidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 5.0, '-', 6.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[7.0, '*', 2.0, '+', 5.0, '-', '-', 6.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[6.0, '*', 2.0, '+', 7.0, '-', 5.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[5.0, '*', 2.0, '+', 6.0, '+', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[6.0, '*', 5.0, '/', 2.0, '-', 7.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\"), ScoredCandidate(candidate=Equation(tokens=[5.0, '+', 6.0, '+', 7.0, '-', 2.0]), score=0, feedback=\"Invalid equation. Error: IndexError('pop from empty list')\")], 'candidates': 'clear'}}\n",
      "Step: {'prune': {'candidates': [ScoredCandidate(candidate=Equation(tokens=[6.0, 5.0, '+', 2.0, '*', 7.0, '-']), score=1.0, feedback='Result: 15.0'), ScoredCandidate(candidate=Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0, '+']), score=1.0, feedback='Result: 15.0'), ScoredCandidate(candidate=Equation(tokens=[6.0, 2.0, '*', 5.0, '-', 7.0, '+']), score=0.9333333333333333, feedback='Result: 14.0')], 'scored_candidates': 'clear', 'depth': 1}}\n"
     ]
    }
   ],
   "source": [
    "config = {\n",
    "    \"configurable\": {\n",
    "        \"thread_id\": \"make15_test\",\n",
    "        \"max_depth\": 10,\n",
    "        \"threshold\": 1.0,\n",
    "        \"k\": 5,\n",
    "        \"beam_size\": 3\n",
    "    },\n",
    "    \"recursion_limit\": 50\n",
    "}\n",
    "\n",
    "# Graph initialization\n",
    "graph = create_graph()\n",
    "\n",
    "# Create a puzzle for testing\n",
    "puzzle = generate_make_puzzles(1, seed=42)[0]\n",
    "print(f\"New puzzle: {puzzle}\")\n",
    "\n",
    "# Run in a stream manner and monitor each step\n",
    "for step in graph.stream({\"problem\": puzzle}, config):\n",
    "    print(f\"Step: {step}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19a6f8cf",
   "metadata": {},
   "source": [
    "Show the final results for the top three scores."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "cbca8d58",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Final Results:\n",
      "--------------------------------------------------\n",
      "Solution 1: [Equation(tokens=[6.0, 5.0, '+', 2.0, '*', 7.0, '-']), 1.0, 'Result: 15.0']\n",
      "Solution 2: [Equation(tokens=[2.0, 7.0, '*', 5.0, '-', 6.0, '+']), 1.0, 'Result: 15.0']\n",
      "Solution 3: [Equation(tokens=[6.0, 2.0, '*', 5.0, '-', 7.0, '+']), 0.9333333333333333, 'Result: 14.0']\n",
      "--------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "def print_results(graph: StateGraph, config: dict):\n",
    "    # Get final status\n",
    "    final_state = graph.get_state(config)\n",
    "    # Extract candidate solutions\n",
    "    candidates = final_state.values[\"candidates\"]\n",
    " \n",
    "    print(\"\\nFinal Results:\")\n",
    "    print(\"-\" * 50)\n",
    "    for i, candidate in enumerate(candidates, 1):\n",
    "        print(f\"Solution {i}: {candidate}\")\n",
    "    print(\"-\" * 50)\n",
    "\n",
    "final_state = graph.get_state(config)\n",
    "best_solution = final_state.values[\"candidates\"][0]  # Extract the highest score answer\n",
    "search_depth = final_state.values[\"depth\"]  # Check search depth\n",
    "\n",
    "\n",
    "print_results(graph, config)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "3.11.9",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
